#include<vector>
#include<iostream>

using namespace std;


 
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};



struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


//深度搜索01：计算布尔二叉树的值
class Solution1 {
public:
    bool evaluateTree(TreeNode* root) 
    {
        if(!root->right&&!root->left)
            return root->val;
        if(root->val==2)
            return evaluateTree(root->left)||evaluateTree(root->right);
        else
            return evaluateTree(root->left)&&evaluateTree(root->right);
    }
};


//深度搜索02：求根节点到叶节点数字之和
class Solution2 {
public:
    int sumNumbers(TreeNode* root) 
    {
        return dfs(root,0);
    }
    int dfs(TreeNode* root,int sum)
    {
        if(!root)   return 0;
            sum=sum*10+root->val;
        if(!root->left&&!root->right)
            return sum;
        return dfs(root->left,sum)+dfs(root->right,sum);
    }
};

//深度搜索03：二叉树剪枝
class Solution3 {
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        return dfs(root);
    }

    TreeNode* dfs(TreeNode* root)
    {
        if(root==nullptr)
            return nullptr;
        if(!root->left&&!root->right)
        {
            if(root->val)   return root;
            else    return nullptr;
        }
        root->left=dfs(root->left);
        root->right=dfs(root->right);
        if(!root->left&&!root->right&&root->val==0) return nullptr;
        else return root;
    }
};

//深度搜索04：验证二叉搜索树
class Solution4 {
public:
    long prev=((long)INT_MIN)-1;
    bool isValidBST(TreeNode* root) 
    {
        if(root==nullptr)
            return true;
        bool left=isValidBST(root->left);
        if(!left)   return false;
        bool mid=root->val>prev;
        if(!mid)    return false;
        else    prev=root->val;
        bool right=isValidBST(root->right);
        if(!right)  return false;
        else return true;
    } 
};


//深度搜索05：二叉搜索树中第K小的元素
class Solution5 {
public:
    int count=0;
    int kthSmallest(TreeNode* root, int k) 
    {
        if(root==nullptr)   return -1;
        if(!root->left&&!root->right)
        {
            count++;
            return root->val;
        }
        int left=kthSmallest(root->left,k);
        if(count==k)    return left;
        count++;
        if(count==k)    return root->val;
        int right=kthSmallest(root->right,k);
        return right;
    }
};

//深度搜索06：二叉树的所有路劲
class Solution6 {
public:
    vector<string>   ret;
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        string path;
        dfs(root,path);
        return ret;
    }

    void dfs(TreeNode* root,string& path)
    {
        if(root==nullptr)   return;
        int oldsize=path.size();        
        path+=to_string(root->val);
        if(!root->left&&!root->right)
            ret.push_back(path);
        else
        {
            path+="->";
            dfs(root->left,path);
            dfs(root->right,path); 
        }       
        path.resize(oldsize);
        return;
    }
};

int main()
{
    return 0;
}